/*
 * @lc app=leetcode id=462 lang=cpp
 *
 * [462] Minimum Moves to Equal Array Elements II
 */

// @lc code=start
class Solution {
public:
    int minMoves2(vector<int>& nums) {
        priority_queue<int, vector<int>,  std::greater<int>> pq;
        int n = nums.size();
        int m;
        m = n / 2 + 1;
        for (auto n : nums){
            if (pq.size() < m) {
                pq.push(n);
            } else {
                if (n > pq.top()){
                    pq.pop();
                    pq.push(n);
                }
            }
        }
        int avg;
        if (n & 1) {
            avg = pq.top();
        } else {
            long a = pq.top();
            pq.pop();
            long b = pq.top();
            avg = (a + b) /2;
        }
        long ans = 0;
        for (auto n : nums) {
            ans += abs(n - avg);
        }
        return ans;      
     

    }
};
// @lc code=end

